import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class project {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum=0;
        int min=Integer.MAX_VALUE;
        int index=0;
        int len=gas.length;
        for(int i=0;i<len;i++){
            sum+=gas[i]-cost[i];
            if(sum<min){
                min=sum;
                index=i;
            }
        }
        if(sum<0){
            return -1;
        }
        return (index+1)%len;
    }
















    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> list=new LinkedList<>();
        int[] flags=new int[numCourses];
        for(int i=0;i<numCourses;i++){
            list.add(new LinkedList<>());
        }
        for(int[] arr:prerequisites){
            list.get(arr[1]).add(arr[0]);
        }
        for(int i=0;i<numCourses;i++){
            if(dfs(i,flags,list)){
                return false;
            }
        }
        return true;
    }
    public boolean dfs(int index,int[] flags,List<List<Integer>> list){
        if(flags[index]==1) {
            return true;
        }
        if(flags[index]==-1){
            return false;
        }
        flags[index]=1;
        for(int value:list.get(index)){
            if(dfs(value,flags,list)){
                return true;
            }
        }
        flags[index]=-1;
        return false;
    }






















    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> list=new LinkedList<>();
        Map<Integer,Integer> map=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            int num=nums[i];
            map.put(num,map.getOrDefault(num,0)+1);
        }
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()>1){
                list.add(entry.getKey());
            }
        }
        return list;
    }
}
